#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class DirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []


class Solution:
    """
    @param: graph: A list of Directed graph node
    @param: s: the starting Directed graph node
    @param: t: the terminal Directed graph node
    @return: a boolean value
    """
    def hasRoute(self, graph, s, t):
        # write your code here
        self.graph = graph
        self.visited = set()

        # return self.dfs_rec_search(s, t)
        return self.bfs_search(s, t)

    # =================== dfs  =====================
    def dfs_rec_search(self, now_at, t):
        if now_at == t:
            return True

        if now_at in self.visited:
            return False

        self.visited.add(now_at)

        for nei in now_at.neighbors:
            is_find = self.dfs_rec_search(nei, t)
            if is_find:
                return True

        return False

    # =================== bfs =====================
    def bfs_search(self, s, t):
        self.queue = [s]

        while self.queue:
            cur = self.queue.pop()
            if cur is t:
                return True

            if cur in self.visited:
                continue

            self.visited.add(cur)
            for nei in cur.neighbors:
                self.queue.append(nei)

        return False


def main():
    print("start main")

    d1 = DirectedGraphNode(1)
    d2 = DirectedGraphNode(2)
    d3 = DirectedGraphNode(3)
    d1.neighbors = [d2]
    d2.neighbors = [d3]

    graph = [d1, d2, d3]
    s = Solution()
    ret = s.hasRoute(graph, d1, d3)
    ret = s.hasRoute(graph, d3, d1)
    print(ret)

if __name__ == "__main__":
    main()
